package org.dslforge.aurum;

import static java.util.Collections.sort;

import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.dslforge.aurum.Automata.Transition;

public final class CharSet implements Cloneable {
	static final CharSet EPSILON = new CharSet();

	public static CharSet any() {
		return new CharSet().add('\u0000', '\uffff');
	}

	Set<Interval> intervals = new HashSet<Interval>();

	public CharSet add(char c) {
		return add(c, c);
	}

	public CharSet add(char start, char end) {
		add(new Interval(start, end));
		return this;
	}

	public CharSet add(CharSet other) {
		for (Interval interval : other.intervals)
			add(interval);
		return this;
	}

	private void add(Interval other) {
		for (Interval interval : intervals)
			if (interval.merge(other))
				return;
			else if (other.merge(interval)) {
				intervals.remove(interval);
				intervals.add(other);
				return;
			}
		intervals.add(other);
	}

	public CharSet remove(char c) {
		return remove(c, c);
	}

	public CharSet remove(char start, char end) {
		for (Interval interval : intervals)
			if (interval.contains(start) || interval.contains(end)) {
				intervals.remove(interval);
				addNewInterval(interval.start, start - 1);
				addNewInterval(end + 1, interval.end);
				break;
			}
		return this;
	}

	private void remove(Interval interval) {
		remove(interval.start, interval.end);
	}

	public CharSet remove(CharSet other) {
		for (Interval interval : other.intervals)
			remove(interval);
		return this;
	}

	public boolean contains(char c) {
		for (Interval interval : intervals)
			if (interval.contains(c))
				return true;
		return false;
	}

	private void addNewInterval(int start, int end) {
		if (start <= end)
			intervals.add(new Interval((char) start, (char) end));
	}

	public boolean isEmpty() {
		return intervals.isEmpty();
	}

	public CharSet negative() {
		return any().remove(this);
	}

	@Override
	public String toString() {
		StringBuffer buffer = new StringBuffer();
		for (Interval interval : intervals)
			buffer.append(interval);
		return buffer.toString();
	}

	@Override
	public Object clone() {
		CharSet cloneOne = new CharSet();
		for (Interval interval : intervals)
			cloneOne.intervals.add(new Interval(interval.start, interval.end));
		return cloneOne;
	}
}

final class Interval {
	char start, end;

	public Interval(char start, char end) {
		this.start = start;
		this.end = end;
	}

	public boolean contains(char c) {
		return start <= c && c <= end;
	}

	public boolean merge(Interval other) {
		if (contains(other.start) || contains(other.end)) {
			start = start < other.start ? start : other.start;
			end = end > other.end ? end : other.end;
			return true;
		}
		if (other.start - end == 1) {
			end = other.end;
			return true;
		}
		return false;
	}

	@Override
	public boolean equals(Object obj) {
		if (obj == null || obj.getClass() != getClass())
			return false;
		Interval interval = (Interval) obj;
		return start == interval.start && end == interval.end;
	}

	@Override
	public int hashCode() {
		return start * 37 + end;
	}

	@Override
	public String toString() {
		return MessageFormat.format("[{0}-{1}]", start, end);
	}
}

class Alphabet {
	static Alphabet alphabet(Automata<CharSet, ?> automata, Collection<Integer> states) {
		Alphabet result = new Alphabet();
		for (Integer state : states)
			for (Transition<CharSet> transition : automata.transitionTable.get(state))
				for (Interval interval : transition.symbols.intervals) {
					result.addPoint(interval.start, true, transition.destination);
					result.addPoint(interval.end, false, transition.destination);
				}
		sort(result.points);
		return result;
	}

	List<Point> points = new ArrayList<Point>();

	Set<Integer> reachableStates = new HashSet<Integer>();

	CharSet symbols;

	private int current = 0;

	boolean next() {
		symbols = null;
		while (current < points.size() && symbols == null) {
			if (points.get(current).start)
				reachableStates.add(points.get(current).destination);
			else {
				reachableStates.remove(points.get(current).destination);
				if (reachableStates.isEmpty()) {
					current++;
					continue;
				}
			}
			symbols = range(points.get(current), points.get(++current));
		}
		return current < points.size();
	}

	void addPoint(char character, boolean start, Integer destination) {
		points.add(new Point(character, start, destination));
	}

	CharSet range(Point start, Point end) {
		int startPoint = (start.start ? start.character : start.character + 1);
		int endPoint = (end.start ? end.character - 1 : end.character);
		return startPoint > endPoint ? null : new CharSet().add((char) startPoint, (char) endPoint);
	}

	class Point implements Comparable<Point> {
		final char character;

		final boolean start;

		final Integer destination;

		Point(char character, boolean start, Integer destination) {
			this.character = character;
			this.start = start;
			this.destination = destination;
		}

		public int compareTo(Point o) {
			if (character == o.character)
				return (start ? (o.start ? 0 : -1) : (o.start ? 1 : 0));
			return character < o.character ? -1 : 1;
		}

		@Override
		public boolean equals(Object obj) {
			if (obj == null || obj.getClass() != getClass())
				return false;
			Point other = (Point) obj;
			return character == other.character && start == other.start
					&& destination == other.destination;
		}

		@Override
		public int hashCode() {
			return (character * 37 + destination.hashCode()) * 37 + (start ? 1 : 0);
		}
	}
}